20220401-TIL

오늘 알고리즘 문제는 페르마의 소정리와 항등식의 성질을 알아야 풀 수 있는 문제였다.

• 이항 계수 3 문제는 이항 계수 계산식을 변형해서 풀었다. (이딴 게 분할정복 유형?)
• 처음에는 동적 계획법 풀이부터 떠올렸는데, 입력 크기가 너무 커서 바로 배제했다..
• 감이 안 와서 질문 게시판까지 찾아봤는데, 그래도 잘 모르겠어서 검색해서 풀었다;
  (나머지 연산은 나눗셈에 대해 분배법칙이 성립하지 않으니, 페르마의 소정리로 식 유도)
• 분할 정복보다는 수학적인 식 유도 과정이 핵심인 문제였다.. (진심으로 벽 느꼈음;)